{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Match Substring After Replacement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: matchReplacement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #替换字符后匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串&nbsp;<code>s</code> 和&nbsp;<code>sub</code>&nbsp;。同时给你一个二维字符数组&nbsp;<code>mappings</code> ，其中&nbsp;<code>mappings[i] = [old<sub>i</sub>, new<sub>i</sub>]</code>&nbsp;表示你可以将&nbsp;<code>sub</code>&nbsp;中任意数目的&nbsp;<code>old<sub>i</sub></code>&nbsp;字符替换为&nbsp;<code>new<sub>i</sub></code>&nbsp;。<code>sub</code>&nbsp;中每个字符 <b>不能</b>&nbsp;被替换超过一次。</p>\n",
    "\n",
    "<p>如果使用 <code>mappings</code>&nbsp;替换 0 个或者若干个字符，可以将 <code>sub</code>&nbsp;变成 <code>s</code>&nbsp;的一个子字符串，请你返回&nbsp;<code>true</code>，否则返回&nbsp;<code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>一个 <strong>子字符串</strong>&nbsp;是字符串中连续非空的字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"fool3e7bar\", sub = \"leet\", mappings = [[\"e\",\"3\"],[\"t\",\"7\"],[\"t\",\"8\"]]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>将 sub 中第一个 'e' 用 '3' 替换，将 't' 用 '7' 替换。\n",
    "现在 sub = \"l3e7\" ，它是 s 的子字符串，所以我们返回 true 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"fooleetbar\", sub = \"f00l\", mappings = [[\"o\",\"0\"]]\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>字符串 \"f00l\" 不是 s 的子串且没有可以进行的修改。\n",
    "注意我们不能用 'o' 替换 '0' 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"Fool33tbaR\", sub = \"leetd\", mappings = [[\"e\",\"3\"],[\"t\",\"7\"],[\"t\",\"8\"],[\"d\",\"b\"],[\"p\",\"b\"]]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>将 sub 里第一个和第二个 'e' 用 '3' 替换，用 'b' 替换 sub 里的 'd' 。\n",
    "得到 sub = \"l33tb\" ，它是 s 的子字符串，所以我们返回 true 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= sub.length &lt;= s.length &lt;= 5000</code></li>\n",
    "\t<li><code>0 &lt;= mappings.length &lt;= 1000</code></li>\n",
    "\t<li><code>mappings[i].length == 2</code></li>\n",
    "\t<li><code>old<sub>i</sub> != new<sub>i</sub></code></li>\n",
    "\t<li><code>s</code> 和&nbsp;<code>sub</code>&nbsp;只包含大写和小写英文字母和数字。</li>\n",
    "\t<li><code>old<sub>i</sub></code> 和&nbsp;<code>new<sub>i</sub></code>&nbsp;是大写、小写字母或者是个数字。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [match-substring-after-replacement](https://leetcode.cn/problems/match-substring-after-replacement/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [match-substring-after-replacement](https://leetcode.cn/problems/match-substring-after-replacement/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"fool3e7bar\"\\n\"leet\"\\n[[\"e\",\"3\"],[\"t\",\"7\"],[\"t\",\"8\"]]', '\"fooleetbar\"\\n\"f00l\"\\n[[\"o\",\"0\"]]', '\"Fool33tbaR\"\\n\"leetd\"\\n[[\"e\",\"3\"],[\"t\",\"7\"],[\"t\",\"8\"],[\"d\",\"b\"],[\"p\",\"b\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mp = set((x, y) for x, y in mappings)\n",
    "        for i in range(len(sub), len(s) + 1):\n",
    "            if all(x == y or (x, y) in mp for x, y in zip(sub, s[i - len(sub): i])):\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        n, m = len(s), len(sub)\n",
    "        dct = defaultdict(set)\n",
    "        for i, j in mappings:\n",
    "            dct[i].add(j)\n",
    "        for i in range(n-m+1):\n",
    "            if all(s[j]==sub[j-i] or s[j] in dct[sub[j-i]] for j in range(i, i+m)):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mp = set((x, y) for x, y in mappings)\n",
    "        for i in range(len(sub), len(s) + 1):\n",
    "            if all(x == y or (x, y) in mp for x, y in zip(sub, s[i - len(sub): i])):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        ms = collections.defaultdict(set)\n",
    "        for x, y in mappings:\n",
    "            ms[y].add(x)\n",
    "        \n",
    "        n = len(s)\n",
    "        m = len(sub)\n",
    "        # print(ms)\n",
    "        for i in range(n - m + 1):\n",
    "            k = i\n",
    "            j = 0\n",
    "            while j < m and (sub[j] == s[k] or sub[j] in ms[s[k]]):\n",
    "                j += 1\n",
    "                k += 1\n",
    "            if j == m:\n",
    "                return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mp = set((x, y) for x, y in mappings)\n",
    "        m, n = len(sub), len(s)\n",
    "        for i in range(n - m + 1):\n",
    "            if all(x == y or (x, y) in mp for x, y in zip(sub, s[i:i+m])):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mp = set((x,y) for x,y in mappings)\n",
    "        for i in range(len(sub),len(s)+1):\n",
    "            if all(x == y or (x,y) in mp for x,y in zip(sub, s[i-len(sub):i])):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def match(s, dic, sub):\n",
    "    for i in range(len(sub)):\n",
    "        if s[i] not in dic[sub[i]]:\n",
    "            return False\n",
    "    return True\t\t\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        dic = {v: [v] for v in sub}\n",
    "\n",
    "        for old, new in mappings:\n",
    "            lst = dic.get(old)\n",
    "            if not lst:\n",
    "                continue\n",
    "            lst.append(new)\n",
    "\n",
    "        for i in range(len(s) - len(sub)+1):\n",
    "            if match(s[i:], dic, sub):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        dic = {v:[v] for v in sub}\n",
    "        for old, new in mappings:\n",
    "            if old in dic:\n",
    "                dic[old].append(new)\n",
    "        for i in range(len(s)-len(sub)+1):\n",
    "            if match(s[i:],dic,sub):\n",
    "                return True\n",
    "        return False\n",
    "def match(s,dic,sub):\n",
    "    for i in range(len(sub)):\n",
    "        if s[i] not in dic[sub[i]]:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        # 1 <= sub.length <= s.length <= 5000\n",
    "        # 暴力就能做啊\n",
    "        m = defaultdict(set)\n",
    "        for old, new in mappings:\n",
    "            m[old].add(new)\n",
    "        \n",
    "        n1 = len(s)\n",
    "        n2 = len(sub)\n",
    "        for i in range(n1):\n",
    "            if n1 - i < n2:\n",
    "                break\n",
    "            for j in range(i, i+n2):\n",
    "                if not (s[j] == sub[j-i] or s[j] in m[sub[j-i]]):\n",
    "                    break\n",
    "                if j == i+n2-1:\n",
    "                    return True\n",
    "        \n",
    "        return False\n",
    "                    \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        for i in range(len(mappings)):\n",
    "            mappings[i]=tuple(mappings[i])\n",
    "        mappings=set(mappings)\n",
    "        for i in range(len(s)-len(sub)+1):\n",
    "\n",
    "            for j in range(len(sub)):\n",
    "                if s[i+j]==sub[j] or (sub[j],s[i+j]) in mappings:\n",
    "                    if j==len(sub)-1:return True\n",
    "                    continue\n",
    "                else:break\n",
    "\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        n = len(s)\n",
    "        m = len(sub)\n",
    "        st = set()\n",
    "        for x, y in mappings:\n",
    "            st.add((x, y))\n",
    "        \n",
    "        #print(f'{st}')\n",
    "        \n",
    "        for i in range(n - m + 1):\n",
    "            k = i\n",
    "            for j in range(m):\n",
    "                #print(f'{(sub[j], s[k])}')\n",
    "                if s[k] != sub[j] and (sub[j], s[k]) not in st:\n",
    "                    break\n",
    "                k += 1\n",
    "            #print(f'{k},{i}')\n",
    "            if k == i + m:\n",
    "                return True\n",
    "        return False\n",
    "           \n",
    "                    \n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def match(s, dic, sub):\n",
    "    if len(s)<len(sub):\n",
    "        return False\n",
    "    for i in range(len(sub)):\n",
    "        if s[i] not in dic[sub[i]]:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings) -> bool:\n",
    "        dic = {v: [v] for v in sub}\n",
    "        for old, new in mappings:\n",
    "            lst = dic.get(old)\n",
    "            if not lst:\n",
    "                continue\n",
    "            lst.append(new)\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if match(s[i:], dic, sub):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        repaly_dict = {}\n",
    "        for mapping in mappings:\n",
    "            c = mapping[0]\n",
    "            repaly_c = mapping[1]\n",
    "            if c not in repaly_dict:\n",
    "                repaly_dict[c] = []\n",
    "            repaly_dict[c].append(repaly_c)\n",
    "        s_index = 0\n",
    "        last_s = \"\"\n",
    "        while s_index <= len(s) - len(sub):\n",
    "            while (s[s_index] != sub[0] and s[s_index] not in repaly_dict.get(sub[0], [])) and s_index < len(s) - len(sub):\n",
    "                s_index += 1\n",
    "            new_s = s[s_index:s_index + len(sub)]\n",
    "            if new_s == last_s:\n",
    "                s_index += 1\n",
    "                continue\n",
    "            for index in range(len(sub)):\n",
    "                if s[s_index + index] == sub[index] or s[s_index + index] in repaly_dict.get(sub[index], []):\n",
    "                    if index == len(sub) - 1:\n",
    "                        return True\n",
    "                    continue\n",
    "                break\n",
    "            last_s = s[s_index:s_index + len(sub)]\n",
    "            s_index += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mapSet = set(f+t for f, t in mappings)\n",
    "        lenSub = len(sub)\n",
    "        for i in range(len(s) - lenSub+1):\n",
    "            for j, subC in enumerate(sub):\n",
    "                sC = s[i+j]\n",
    "                if sC != subC and (subC+sC) not in mapSet:\n",
    "                    break\n",
    "            else:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mp = set((x, y) for x, y in mappings)\n",
    "        for i in range(len(sub), len(s) + 1):\n",
    "            if all(x == y or (x, y) in mp for x, y in zip(sub, s[i - len(sub): i])):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mp = set((x, y) for x, y in mappings)\n",
    "        for i in range(len(sub), len(s) + 1):\n",
    "            if all(x == y or (x, y) in mp for x, y in zip(sub, s[i - len(sub): i])):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        n, m = len(s), len(sub)\n",
    "        d = {}\n",
    "        for u, v in mappings:\n",
    "            if u in d.keys():\n",
    "                d[u].add(v)\n",
    "            else:\n",
    "                d[u] = {v}\n",
    "        def match(s1, s2):\n",
    "            for i in range(m):\n",
    "                if s1[i] == s2[i] or (s1[i] in d.keys() and s2[i] in d[s1[i]]):\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(n - m + 1):\n",
    "            if match(sub, s[i:i+m]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mp = set((x, y) for x, y in mappings)\n",
    "        m, n = len(sub), len(s)\n",
    "        for i in range(m, n + 1):\n",
    "            if all(x == y or (x, y) in mp for x, y in zip(sub, s[i-m:i])):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        n = len(s)\n",
    "        m = len(sub)\n",
    "        d = defaultdict(list)\n",
    "        # O(m)\n",
    "        for x,y in mappings:\n",
    "            d[x].append(y)\n",
    "        # O(n)\n",
    "        def check(cur,sub):\n",
    "            for i in range(m):\n",
    "                if cur[i] != sub[i] and cur[i] not in d[sub[i]]:\n",
    "                    return False\n",
    "            return True\n",
    "        # O(n)\n",
    "        for i in range(0,n-m+1):\n",
    "            cur = s[i:i+m]\n",
    "            if check(cur,sub):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        n,m = len(s),len(sub)\n",
    "        dic = defaultdict(set)\n",
    "        for s1,s2 in mappings:\n",
    "            dic[s1].add(s2)\n",
    "        for i in range(n-m+1):\n",
    "            for j in range(i,i+m):\n",
    "                if not (s[j] == sub[j-i] or (sub[j-i] in dic and s[j] in dic[sub[j-i]])):\n",
    "                    break\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        n,m = len(s),len(sub)\n",
    "        dic = {}\n",
    "        for s1,s2 in mappings:\n",
    "            if s1 not in dic:\n",
    "                dic[s1] = set()\n",
    "            dic[s1].add(s2)\n",
    "        for i in range(n-m+1):\n",
    "            for j in range(i,i+m):\n",
    "                if not (s[j] == sub[j-i] or (sub[j-i] in dic and s[j] in dic[sub[j-i]])):\n",
    "                    break\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mp=set((x,y) for x,y in mappings)\n",
    "        sb=len(sub)\n",
    "        for i in range(len(s)-len(sub)+1):\n",
    "            if all(x==y or (x,y) in mp for x,y in zip(sub,s[i:i+sb])):\n",
    "                return True\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mp = set((x, y) for x, y in mappings)\n",
    "        for i in range(len(sub), len(s) + 1):\n",
    "            if all(x == y or (x, y) in mp for x, y in zip(sub, s[i - len(sub): i])):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mp = set((x, y) for x, y in mappings)\n",
    "        print(mp)\n",
    "        for i in range(len(sub), len(s) + 1):\n",
    "            if all( x == y or (x, y) in mp for x, y in zip((sub), s[i - len(sub):i])):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        mapping_dict = {}\n",
    "        for old, new in mappings:\n",
    "            if old not in mapping_dict:\n",
    "                mapping_dict[old] = [new]\n",
    "            else:\n",
    "                mapping_dict[old].append(new)\n",
    "                \n",
    "        def is_match(s_sub, sub):\n",
    "            for i in range(len(sub)):\n",
    "                if s_sub[i] != sub[i] and sub[i] in mapping_dict:\n",
    "                    if s_sub[i] not in mapping_dict[sub[i]]:\n",
    "                        return False\n",
    "                elif s_sub[i] != sub[i]:\n",
    "                    return False\n",
    "            return True\n",
    "                \n",
    "        for i in range(len(s) - len(sub) + 1):\n",
    "            if is_match(s[i:i + len(sub)], sub):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        d = defaultdict(set)\n",
    "        for a,b in mappings:\n",
    "            d[a].add(b)\n",
    "        \n",
    "        m, n = len(s), len(sub)\n",
    "        def check(i):\n",
    "            for j,v in enumerate(sub):\n",
    "                if s[i+j] != v and s[i+j] not in d[v]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        for i in range(m-n+1):\n",
    "            if check(i):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        d = defaultdict(set)\n",
    "        for ma, mb in mappings:\n",
    "            d[ma].add(mb)\n",
    "        \n",
    "        n = len(s)\n",
    "        m = len(sub)\n",
    "        for i in range(n - m + 1):\n",
    "            if all(x == y or x in d[y] for x, y in zip(s[i:], sub)):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        left = 0\n",
    "        dct = dict()\n",
    "        for a, b in mappings:\n",
    "            if a not in dct:\n",
    "                dct[a] = set([b])\n",
    "            else:\n",
    "                dct[a].add(b)\n",
    "        n = len(s)\n",
    "        # print(dct)\n",
    "        for i in range(n - len(sub) + 1):\n",
    "            for j in range(len(sub)):\n",
    "                if sub[j] != s[i + j] and s[i + j] not in dct.get(sub[j], set()):\n",
    "                    break\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        cs = {c:set([c]) for c in set(s)}\n",
    "        for old, new in mappings :\n",
    "            if new in cs :\n",
    "                cs[new].add(old)\n",
    "        for ps in range(len(s)-len(sub)+1) :\n",
    "            mark = True\n",
    "            for j in range(len(sub)) :\n",
    "                if not sub[j] in cs[s[ps+j]] :\n",
    "                    mark = False\n",
    "                    break\n",
    "            if mark :\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        maps = set((x, y) for x, y in mappings)\n",
    "        def check():\n",
    "            #print(s[i - len(sub) + 1: i + 1], sub)\n",
    "            for x, y in zip(sub, s[i - len(sub) + 1: i + 1]):\n",
    "                if x == y: continue\n",
    "                if (x, y) in maps: continue\n",
    "                print(x, y)\n",
    "                return False\n",
    "            return True \n",
    "        for i in range(len(sub) - 1, len(s)):\n",
    "            if check(): return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        d = set((x,y) for x,y in mappings)\n",
    "        n = len(s)\n",
    "        m = len(sub)\n",
    "        # 枚举\n",
    "        for i in range(m,n+1):\n",
    "            if all((x,y) in d or x == y for x,y in zip(sub,s[i-m:i])):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        n = len(s)\n",
    "        m = len(sub)\n",
    "        st = set((x,y) for x, y in mappings)\n",
    "        \n",
    "        for i in range(n - m + 1):\n",
    "            k = i\n",
    "            for j in range(m):\n",
    "                #print(f'{(sub[j], s[k])}')\n",
    "                if s[k] != sub[j] and (sub[j], s[k]) not in st:\n",
    "                    break\n",
    "                k += 1\n",
    "            #print(f'{k},{i}')\n",
    "            if k == i + m:\n",
    "                return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        old = [0]*128\n",
    "        new = [0]*128\n",
    "        for i, c in enumerate(s):\n",
    "            new[ord(c)] |= 1 << i\n",
    "        for i in range(128):\n",
    "            old[i] |= new[i]\n",
    "        for c1, c2 in mappings:\n",
    "            old[ord(c1)] |= new[ord(c2)]\n",
    "        ans = old[ord(sub[0])]\n",
    "        for i, c in enumerate(sub):\n",
    "            ans &= old[ord(c)] >> i\n",
    "        return ans > 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        old = [0]*128\n",
    "        new = [0]*128\n",
    "        for i, c in enumerate(s):\n",
    "            new[ord(c)] |= 1 << i\n",
    "        for i in range(128):\n",
    "            old[i] |= new[i]\n",
    "        for c1, c2 in mappings:\n",
    "            old[ord(c1)] |= new[ord(c2)]\n",
    "        ans = old[ord(sub[0])]\n",
    "        for i, c in enumerate(sub):\n",
    "            ans &= old[ord(c)] >> i\n",
    "        return ans > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        Mp = defaultdict(set)\n",
    "        ls,lsub = len(s),len(sub) \n",
    "        for a,b in mappings:\n",
    "            Mp[a].add(b)\n",
    "        for i in sub:Mp[i].add(i)\n",
    "            \n",
    "        probpos = []\n",
    "        cur = 0\n",
    "        for idx in range(ls):\n",
    "            i = s[idx]\n",
    "            if i in Mp[sub[cur]]:probpos.append(idx)\n",
    "        cur = 1\n",
    "        while probpos and cur < len(sub):\n",
    "            temp = probpos\n",
    "            probpos = []\n",
    "            for i in temp:\n",
    "                if i+1 < ls and s[i+1] in Mp[sub[cur]]:probpos.append(i+1)\n",
    "            cur += 1\n",
    "        return bool(cur == len(sub) and len(probpos))\n",
    "                \n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        s_indexs=defaultdict(list)\n",
    "        for index,char in enumerate(s):\n",
    "            s_indexs[char].append(index)\n",
    "        map_dict=defaultdict(list)   \n",
    "        for old,new in mappings:\n",
    "            map_dict[old].append(new)\n",
    "        \n",
    "        default_set=set(range(len(s)))\n",
    "        for idx,ch in enumerate(sub):\n",
    "            set_a=set()\n",
    "            if ch in s_indexs:\n",
    "                set_a.update([x-idx for x in s_indexs[ch]])\n",
    "            if ch in map_dict:\n",
    "                for new_ch in map_dict[ch]:\n",
    "                    if new_ch in s_indexs:\n",
    "                        set_a.update([x-idx for x in s_indexs[new_ch]])\n",
    "            default_set &=set_a\n",
    "        return True if default_set else False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        d=defaultdict(list)\n",
    "        p=defaultdict(list)\n",
    "        ans=set()\n",
    "        for i,j in mappings:\n",
    "            d[i].append(j)\n",
    "        for i,x in enumerate(s):\n",
    "            p[x].append(i)\n",
    "        for i,x in enumerate(sub):\n",
    "            if i==0:\n",
    "                for j in d[x]:\n",
    "                    if j in p:\n",
    "                        for k in p[j]:\n",
    "                            ans.add(k)\n",
    "                if x in p:\n",
    "                    for k in p[x]:\n",
    "                        ans.add(k)\n",
    "            else:\n",
    "                fok=set()\n",
    "                for j in d[x]:\n",
    "                    if j in p:\n",
    "                        for k in p[j]:\n",
    "                            if k-i in ans:\n",
    "                                fok.add(k-i)\n",
    "                if x in p:\n",
    "                    for k in p[x]:\n",
    "                        if k-i in ans:\n",
    "                            fok.add(k-i)\n",
    "                if not fok:\n",
    "                    return False\n",
    "                else:\n",
    "                    ans=fok\n",
    "        if ans:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(\n",
    "        self, s: str, sub: str, mappings: List[List[str]]\n",
    "    ) -> bool:\n",
    "\n",
    "        slen, sublen = len(s), len(sub)\n",
    "\n",
    "        hashmap = defaultdict(list)\n",
    "        for old, new in mappings:\n",
    "            hashmap[old].append(new)\n",
    "\n",
    "        starts = set([sub[0]] + hashmap[sub[0]])\n",
    "        subrest = [set([ch] + hashmap[ch]) for ch in sub[1:]]\n",
    "\n",
    "        for i in range(slen - sublen + 1):\n",
    "            if s[i] in starts:\n",
    "                cursub = s[i + 1: i + sublen]\n",
    "                for ch, chlist in zip(cursub, subrest):\n",
    "                    if ch not in chlist:\n",
    "                        break\n",
    "                else:\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:\n",
    "        trans = defaultdict(str)\n",
    "        for mp in mappings:\n",
    "            trans[mp[0]] += mp[1]\n",
    "        \n",
    "        rep = \"\"\n",
    "        for x in sub:\n",
    "            if trans[x] == \"\":\n",
    "                rep += x\n",
    "            else:\n",
    "                rep += f\"[{trans[x]}{x}]\"\n",
    "        \n",
    "        m = re.search(rep, s)\n",
    "        print(rep)\n",
    "        return m is not None"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
